Unió i intersecció de llenguatges regulars – la construcció del producte
Donat un mot w\in \{a,b\}^*, sigui L_w=\{xwy\mid x,y\in\{a,b\}^*\}. En altres paraules, L_w és el llenguatge dels mots que contenen w com a submot.
Demostreu que per tot mot w, L_w és un llenguatge regular.
Construïu DFAs mínims que reconeguin els llenguatges següents. Demostreu que els DFAs construïts són correctes i tenen el nombre més petit possible d’estats.
- L_{a}
- L_{aa}
- L_{aaa}
Fent servir la construcció del producte cartesià, contruïu DFAs que reconeguin els llenguatges següents i minimitzeu els DFAs obtinguts.
- L_{aa}\cup L_{bb}
- L_{a}\cup L_{bbb}
Què canviaria en cas de voler els llenguatges L_{aa}\cap L_{bb} and L_{a}\cap L_{bbb}?
Donats dos DFAs A i B com a entrada, quin és el cost de calcular un DFA per L(A)\cup L(B) i L(A)\cap L(B) fent servir la construcció del producte cartesià?
Donats DFAs mínims A i B, és el DFA que reconeix L(A)\cup L(B) obtingut amb la construcció del producte d’A i B mínim? Què es pot dir del DFA per L(A)\cap L(B)?
Què passa si apliquem la construcció del producte cartesià a NFAs en lloc de DFAs? Dona també la construcció del producte de NFAs un bon NFA per la unió (resp. intersecció)?